package 力扣91;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * @ClassName : Day_18_987_二叉树的垂序遍历
 * @Author : 骆发茂
 * @Date: 2021/12/29 22:18
 * @Description : https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree/
 */
public class Day_18_987_二叉树的垂序遍历 {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */


    /**遍历整个树，用list<int[]>  记录每个节点的行号 row，列号 col 以及值 value
     * 之后进行排序，Collections.sort(nodes, new Comparator<int[]>()
     * 按照 col 为第一关键字升序，row 为第二关键字升序，value 为第三关键字升序，对所有的节点进行排序*/
    class Solution {
        public List<List<Integer>> verticalTraversal(TreeNode root) {
            List<int[]> nodes = new ArrayList<int[]>();
            //对整棵树进行一次遍历，在遍历的过程中使用数组 nodes 记录下每个节点的行号 row，列号 col 以及值 value
            dfs(root, 0, 0, nodes);

            Collections.sort(nodes, new Comparator<int[]>() {
                public int compare(int[] tuple1, int[] tuple2) {
                    //nodes.add(new int[]{col, row, node.val});
                    //当列不同的时候
                    //比较的是list中，每一个小int[]，tuple就是一个int[]
                    if (tuple1[0] != tuple2[0]) {
                        return tuple1[0] - tuple2[0];
                    }
                    //当列相同的时候，比较行的情况
                    else if (tuple1[1] != tuple2[1]) {
                        return tuple1[1] - tuple2[1];
                    }
                    //行列都相同，比较值
                    else {
                        return tuple1[2] - tuple2[2];
                    }
                }
            });
            List<List<Integer>> ans = new ArrayList<List<Integer>>();
            int size = 0;
            int lastcol = Integer.MIN_VALUE;
            /**对 nodes 进行一次遍历，并在遍历的过程中记录上一个节点的列号 lastcol。
             * 如果当前遍历到的节点的列号 col 与 lastcol 相等，
             * 则将该节点放入与上一个节点相同的数组中，
             * 否则放入不同的数组中*/
            for (int[] tuple : nodes) {
                int col = tuple[0], row = tuple[1], value = tuple[2];
                if (col != lastcol) {
                    lastcol = col;
                    ans.add(new ArrayList<Integer>());
                    size++;
                }
                ans.get(size - 1).add(value);
            }
            return ans;
        }


        //对整棵树进行一次遍历，在遍历的过程中使用数组 nodes 记录下每个节点的行号 row，列号 col 以及值 value
        public void dfs(TreeNode node, int row, int col, List<int[]> nodes) {
            if (node == null) {
                return;
            }
            nodes.add(new int[]{col, row, node.val});
            dfs(node.left, row + 1, col - 1, nodes);
            dfs(node.right, row + 1, col + 1, nodes);
        }

    }
}